LeetCode——计算质数

NO.204 计算质数简单

思路一：暴力法 双层for循环。1.第一层循环遍历逐个判断[2,n)。2.第二层循环判断参数是否为素数。：

public int countPrimes(int n){
    int count=0;
    for (int i=2;i<n;i++){
        if (isPrime(i))
            count++;
    }
    return count;
}

public boolean isPrime(int n){
    for(int i=2;i<n;i++){
        if (n%i==0)return false;
    }
    return true;
}

时间复杂度:O(n^2)

可改进点：例如，12=2*6、12=3*4、12=sqrt(12)*sqrt(12)、12=4*3、12=62，可以观察到后面就是前面两个数反过来，说明查找可以整除12的因子时只需要找到“一半”的位置即可，如果前“一半”没有可以整除的因子，那么后“一半”也没有，这个临界点“一半”就是sqrt(12)。所以上述isPrime()方法的循环条件可以写为“i\i<n”即可，该方法时间复杂度降到了O(sqrt(n))。

思路二：厄拉多塞筛法 不难想象，所有质数的倍数都不是质数。例如，2是质数，2的倍数4、6、8、10、12。。。都不是质数；3是质数，3的倍数6、9、12、15。。。都不是质数；可以看一下维基百科中一个厄拉多塞筛的gif图：

这种方法大概就是“排除法”，每确定一个质数，就可以排除一批非质数，那么算法就可以这么写：

public int countPrimes(int n){
        boolean isPrimes[]=new boolean[n];
        Arrays.fill(isPrimes,true);
//		将所有质数的倍数设置为false
        for (int i=2;i<n;i++){
            for (int j=i;j<n;j+=i){
                isPrimes[j]=false;
            }
        }
        int count=0;
//      统计所有质数，即isPrimes[i]==true的为质数
        for (int i=2;i<n;i++){
            if (isPrimes[i])count++;
        }
        return count;
    }

上述算法还存在两处冗余：

在本题的暴利算法下说的：只需要判断到sqrt(n)即可。
例如，12不是质数，所以会被设置为false，但是12既是2的倍数，也是3的倍数，所以它被标记了两次。

解决上述两处冗余后的算法：

public int countPrimes(int n){
        boolean isPrimes[]=new boolean[n];
        Arrays.fill(isPrimes,true);
//        只需要判断小于sqrt(n)的数是否为质数即可，所以i*i<n
        for (int i=2;i*i<n;i++){
//            这样可以把质数i的整数倍都标记为false，但是仍然存在计算冗余。
//            比如n=25，i=4时算法会标记4×2=8，4×3=12等等数字，
//            但是这两个数字已经被i=2和i=3的2×4和3×4标记了。所以使用j=i*i减少此计算的冗余。
            for (int j=i*i;j<n;j+=i){
                isPrimes[j]=false;
            }
        }
        int count=0;
//      统计所有质数，即isPrimes[i]==true的为质数
//        这里要注意从2开始，因为0,1不是质数
        for (int i=2;i<n;i++){
            if (isPrimes[i])count++;
        }
        return count;
    }

厄尔拉塞筛法的时间复杂度：O(nloglogn)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.204 计算质数 简单

NO.204 计算质数简单